#include"head.h"

void Sudoku::initSudoku()
{
    // 将变量置零
    memset(rows, 0, sizeof(rows));
    memset(columns, 0, sizeof(columns));
    memset(blocks, 0, sizeof(blocks));
    spaces.clear();
    result.clear();
}

void Sudoku::addResult(Board& board) // 向result添加结果
{
    vector<vector<char> > obj(board);
    result.push_back(obj);
}

void Sudoku::flip(int i, int j, int digit)
{
    // 对记录数组取反
    rows[i][digit] = !rows[i][digit];
    columns[j][digit] = !columns[j][digit];
    blocks[(i / 3) * 3 + j / 3][digit] = !blocks[(i / 3) * 3 + j / 3][digit];
}

vector<Board> Sudoku::solveSudoku(Board board)
{
    initSudoku();
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] == '$')
            {
                spaces.push_back(pair<int, int>(i, j));
            }
            else
            {
                int digit = board[i][j] - '1';
                flip(i, j, digit);
            }
        }
    }
    DFS(board, 0);
    return result;
}

void Sudoku::DFS(Board& board, int pos) // 深度优先
{
    if (pos == spaces.size())
    {
        addResult(board);
        return;
    }
    int i = spaces[pos].first;
    int j = spaces[pos].second;

    bool left[9]; // 剩余可用数字
    memset(left, 0, sizeof(left));
    for (int k = 0; k < 9; k++) // 如果可填k则left[k]为1
    {
        if (rows[i][k] || columns[j][k] || blocks[(i / 3) * 3 + j / 3][k]) // 判断数字是否可用
            left[k] = false;
        else
            left[k] = true;
    }
    int digit = 0;
    for (int k = 0; k < 9; k++) // 剩下的是几就记录并dfs
    {
        if (left[k])
        {
            flip(i, j, digit);
            board[i][j] = '1' + digit;
            DFS(board, pos + 1);
            flip(i, j, digit);
        }
        digit++;
    }
}

bool Sudoku::checkBoard(Board& board)
{
    initSudoku();
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (board[i][j] != '$')
            {
                int digit = board[i][j] - '1';
                if ((rows[i][digit] || columns[j][digit] || blocks[(i / 3) * 3 + j / 3][digit]))
                {
                    return false;
                }
                flip(i, j, digit);
            }
        }
    }
    return true;
}

void Sudoku::printBoard(Board& board)
{
    for (size_t i = 0; i < board.size(); i++)
    {
        for (size_t j = 0; j < board[i].size(); j++)
        {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
}

Board Sudoku::generateBoard(int holes, bool mustUnique)
{
    vector<vector<char> > board(N, vector<char>(N, '$'));
    vector<int> row = getRand9();
    for (size_t i = 0; i < 3; i++)
    {
        board[3][i + 3] = row[i] + '1';
        board[4][i + 3] = row[i + 3] + '1';
        board[5][i + 3] = row[i + 6] + '1';
    }
    copySquare(board, 3, 3, true);
    copySquare(board, 3, 3, false);
    copySquare(board, 3, 0, false);
    copySquare(board, 3, 6, false);

    while (holes)
    {
        int x = rand() % 9;
        int y = rand() % 9;
        if (board[x][y] == '$')
            continue;
        char tmp = board[x][y];
        board[x][y] = '$';

        solveSudoku(board);
        if (!mustUnique || mustUnique && result.size() == 1)
        {
            holes--;
        }
        else
        {
            board[x][y] = tmp;
        }
    }
    if (!checkBoard(board))
    {
        cout << "wrong board" << endl;
    }

    return board;
}

vector<int> Sudoku::getRand9()
{
    vector<int> result;
    bool nums[9];
    memset(nums, 0, sizeof(nums));
    while (result.size() != 9)
    {
        int num = rand() % 9;
        if (nums[num])
        {
            continue;
        }
        else
        {
            result.push_back(num);
            nums[num] = true;

        }
    }
    return result;
}

void Sudoku::copySquare(Board& board, size_t src_x, size_t src_y, bool isRow)
{
    size_t rand_tmp = size_t(rand()) % 2 + 1;
    size_t order_first[3] = { 1, 2, 0 };
    size_t order_second[3] = { 2, 0, 1 };
    if (rand_tmp == 2)
    {
        order_first[0] = 2;
        order_first[1] = 0;
        order_first[2] = 1;
        order_second[0] = 1;
        order_second[1] = 2;
        order_second[2] = 0;
    }
    for (size_t i = 0; i < 3; i++)
    {
        if (isRow)
        {
            board[src_x][i] = board[src_x + order_first[0]][src_y + i];
            board[src_x + 1][i] = board[src_x + order_first[1]][src_y + i];
            board[src_x + 2][i] = board[src_x + order_first[2]][src_y + i];
            board[src_x][i + 6] = board[src_x + order_second[0]][src_y + i];
            board[src_x + 1][i + 6] = board[src_x + order_second[1]][src_y + i];
            board[src_x + 2][i + 6] = board[src_x + order_second[2]][src_y + i];
        }
        else
        {
            board[i][src_y] = board[src_x + i][src_y + order_first[0]];
            board[i][src_y + 1] = board[src_x + i][src_y + order_first[1]];
            board[i][src_y + 2] = board[src_x + i][src_y + order_first[2]];
            board[i + 6][src_y] = board[src_x + i][src_y + order_second[0]];
            board[i + 6][src_y + 1] = board[src_x + i][src_y + order_second[1]];
            board[i + 6][src_y + 2] = board[src_x + i][src_y + order_second[2]];
        }
    }
}

vector<Board> readFile(string filePath)
{
    ifstream infile;
    vector<Board> boards;
    infile.open(filePath);
    char data[100];
    Board tmp;
    vector<char> row;
    while (!infile.eof())
    {
        infile.getline(data, 100);
        if (data[0] == '-')
        {
            boards.push_back(Board(tmp));
            tmp.clear();
            continue;
        }
        for (size_t i = 0; i < strlen(data); i++)
        {
            if (('1' <= data[i] && data[i] <= '9') || data[i] == '$')
            {
                row.push_back(data[i]);
            }
        }
        tmp.push_back(vector<char>(row));
        row.clear();
    }
    infile.close();
    return boards;
}

void writeFile(vector<Board> boards, ofstream& f)
{
    for (size_t k = 0; k < boards.size(); k++)
    {
        for (size_t i = 0; i < boards[k].size(); i++)
        {
            for (size_t j = 0; j < boards[k][i].size(); j++)
            {
                f << boards[k][i][j] << " ";
            }
            f << "\n";
        }
        f << "-----------------" << endl;
    }
}

void generateGame(int gameNum, vector<int> digCount, ofstream& outfile, Sudoku& s, bool mustUnique)
{
    for (int i = 0; i < gameNum; i++)
    {
        int cnt = 0;
        if (digCount.size() == 1)
        {
            cnt = digCount[0];
        }
        else
        {
            cnt = rand() % (digCount[1] - digCount[0] + 1) + digCount[0];
        }
        Board board = s.generateBoard(cnt, mustUnique);
        vector<Board> boards;
        boards.push_back(board);
        writeFile(boards, outfile);
    }
    outfile.close();
}

